时间差分控制
时间差分算法结合了动态规划和MC的特点：它同样不需要模型，只需要跟环境进行交互，通过自举（bootstrap）解决预测问题和估计问题。时间差分控制与蒙特卡罗最大的不同在于前者能够在生成episode的过程中利用前后状态的信息对动作值函数进行改进更新，这两个特点使得TD支持在线的增量计算 （incremental computation），这是符合现实应用中大部分场景的需求的。
TD(0)
根据值函数的表达式：
TD(0)正是为了估计上述表达式，当前状态为$S_t$时，根据当前策略执行相应的动作，获得立即回报$R_{t+1}$以及当前状态的值函数估计值$V(S_{t+1})$，利用获得的时间差分信息$R_{t+1} + \lambda V(S_{t+1}) - V(S_t)$对当前的值函数进行更新：
具体的算法流程如下：
从上述算法可以看到TD(0)的两个特点：不需要模型，且支持在线增量学习。第一个特点使得TD(0)能够应用大多数的实际场景下，第二个特点使得值函数的计算周期减小为一个time-step。
将TD(0)算法应用到估计问题上时，根据行为策略和估计策略的不同分为在线策略和离线策略两种，代表算法分别是SARSA学习算法和Q-学习算法。
Q-学习
从算法可以发现，它需要的经验样本为$(s, a, r, s’)$
SARSA 学习
sarsa学习算法需要的经验样本为$(s, a, r, s’, a’)$
TD($\lambda$)
n-步TD
第一部分的TD(0)也成为1-步TD，因为它总是需要后一时刻的回报值$R_{t+1}$以及后面一个状态的估计值函数$V(S_{t+1})$来更新当前的状态值函数$V(S_t)$，而在MC中，我们总是在episode结束后根据状态$S_t$后面一直到终止状态为止的所有回报值来估计当前的值函数$V(S_t)$。n-步TD正是为了描述这两种极端的估计方法之间的其他方法，如下图所示。
图中空心圆表示状态，实心圆表示动作。当我们处在状态$S_t$，希望利用到后面$n$个时间步之后的回报值$R_i, i=t+1, \ldots, t+n$以及$t+n$时刻的值函数估计值$V(S_{t+n})$来更新当下的值函数$S_t$时，对应的更新方式为：
其中$G_t^{(n)}$称为n-步回报（n-step return），它的计算方式为：
A forward view
n-step TD中，我们根据$G_t^{(n)}$的值能够完成值函数的更新。如果希望综合多个$G_t^{(i)}，i = t+1, t+2, \ldots$的信息来估计值函数时，需要利用加权的方式进行计算，重点在于权重之和必须为1。TD($\lambda$)算法是一种特定对多个i-步回报加权求和的方法，它具有一组特定的权重序列，对应的i-步回报如下图所示：
我们称这种综合的回报信息为$\lambda$-回报（$\lambda$-return），它表示为：
TD($\lambda$)下状态值的更新方式与TD(0)的方式一致，不同的地方在于时间差分变为$G_t^{\lambda} - V(S_t)$，下图形象的描述了该算法（$\lambda$-回报算法）的思想：
A backward view
上一小节中$G_t^{\lambda}$实际上应用时存在问题，即便是在episode任务中，它也必须在一个完整的episode结束后才能开始值函数更新，因此不支持在线学习。为了解决这个问题，引入额外的记忆变量资格迹（eligibility trace），通过每个状态的资格迹将$G_t^{\lambda}$等价的转换为方便在线学习的形式：
其中资格迹$Z_t(s)$有两种常用的形式：
前者称为accumulating trace，后者叫replacing trace，唯一的区别在于：前者将当前状态$S_t$的资格迹乘上decay权重$\gamma \lambda$后再加上1，而后者直接将其重置为1。两者处理非当前状态$s \ne S_t$的资格迹的方式一致。两者的对比如下图所示：
通过引入资格迹，使得TD($\lambda$)算法能够应用到在线学习环境中，在当前时刻$t$，根据所有状态对应的历史资格迹$Z_{t-1}(s)$更新当前的资格迹值，并更新当前状态的值函数$V(S_t)$，对于其他的非当前状态$s \ne S_t$则通过资格迹的更新来记录历史信息，这个过程的示意图如下，与forward的视角不同的地方在于，forward在当前时刻只更新$V(S_t)$，它需要后续所有时刻的信息，这个更新操作实际上发生在episode结束后，而backward的视角则只需要后一时刻的回报值和状态值更新当前时刻的值函数，同时更新所有其他状态的资格迹，以备在未来时刻出现相应的状态时进行值函数更新，相当于用空间换时间。
Sarsa($\lambda$)
前面介绍的资格迹只定义在状态集上，为了将其应用在RL的控制问题上，需要将资格迹的定义扩展到（状态，动作）对上，其中accumulating trace和replacing trace对应的定义分别如下：
结合资格迹和在线的Sarsa算法称为Sarsa($\lambda$)算法，它的算法流程如下：
上述算法中对于资格迹的实现方式似乎与定义不同，因为算法是先进行加1的操作，然后对所有的资格迹值乘$\gamma \lambda$，乍看，这与定义中的顺序是不一致的，定义中是先乘上$\gamma \lambda$再对特定的资格迹加上1。实际上，要注意的是定义中对当前时刻$t$的资格迹的更新是基于前一时刻$t-1$的值进行的，也就是说$\gamma \lambda Z_{t-1}(s,a)$是在上一次迭代中提前计算好的，当我们执行完算法中$Z(S,A) \leftarrow Z(S,A) + 1$这一步时，已经完成了对$Z_t(s,a)$的全部更新，后面的更新操作$Z(s,a) \leftarrow \gamma \lambda Z(S,A)$是在为下一时刻即$t+1$时刻的资格迹更新做准备。
Q($\lambda$)
Q-学习算法因为是离线学习算法，因此相应的资格迹定义为：
其中$I_{xy}$为示性函数，当$x=y$时等于1，否则等于0. 这种资格迹定义下的学习算法称为Watkins‘s Q($\lambda$)算法，它的思路是：只要是当前状态下的动作$A_t$是符合贪婪策略的，则对资格迹整体进行更新$Z_t(s,a) = 1 + \gamma \lambda Z_{t-1}(s, a)$，否则，$Z_{t-1}(S_t, A_t)$加1，而其他状态下的动作对应的资格迹全部重置为0，也就是说此时的资格迹只能记录到下一次探索动作发生时的信息，一旦发生探索动作，则丢弃之前的信息，重新记录，如果在与环境的交互过程中频繁的出现探索动作（一般出现在策略初期），则资格迹只能够记录很短时间内的信息，这会导致动作值函数的学习非常缓慢。资格迹的作用范围如下图所示：
对应的算法流程如下：
参考文献
1、Richard S. Sutton. Reinforcement learning An introduction. Second edition. MIT Press;